|
In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number χH(''G'') of a graph ''G'' is the minimum number of colors needed for any harmonious coloring of ''G''. Every graph has a harmonious coloring, since it suffices to assign every vertex a distinct color; thus χH(''G'') ≤ |V(G)|. There trivially exist graphs ''G'' with χH(''G'') > χ(''G'') (where χ is the chromatic number); one example is the path of length 2, which can be 2-colored but has no harmonious coloring with 2 colors. Some properties of χH(''G''): # χH(T''k'',3) = ⌈(3/2)(''k''+1)⌉, where T''k'',3 is the complete ''k''-ary tree with 3 levels. (Mitchem 1989) Harmonious coloring was first proposed by Harary and Plantholt (1982). Still very little is known about it. ==See also== * Complete coloring * Harmonious labeling 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「harmonious coloring」の詳細全文を読む スポンサード リンク
|